package com.waitingresult.zuo;

/**
 * @Author: WangShuai
 * @CreateTime: 2022-11-08  11:38
 * @Description:
 * @Version: 1.0
 */
public class PrefixArrDemo { // 前缀

    public static void main(String[] args) {
        // 给定一个数组， 给定 起始位置和终止位置， 求累加和
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        //1 2 3 4 5 6 7 8 9
        //1 3 6 10 15 21 28 36 45
        System.out.println(search(arr, 1, 3));

    }

    public static int search(int[] arr, int start, int end) {
        int[] helpArr = getHelpArr(arr);
//        SortUtils.print(arr);
//        SortUtils.print(helpArr);
        return helpArr[end] - helpArr[start];
    }

    private static int[] getHelpArr(int[] arr) {
        int[] h = new int[arr.length];
        h[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            h[i] = arr[i] + h[i - 1];
        }
        return h;
    }
}
